package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.Unknown;

import java.util.Arrays;
import java.util.concurrent.ThreadLocalRandom;

/**
 * @author tzp
 * @since 2020/10/29
 */
public class LC16 implements Unknown {
    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int off = Integer.MAX_VALUE;
        for (int i = 0; i < nums.length; i++) {
            int lo = i + 1, hi = nums.length - 1;
            while (lo < hi) {
                int sum = nums[i] + nums[lo] + nums[hi];
                if (sum == target) return target;
                if (Math.abs(target - sum) < Math.abs(off)) {
                    off = target - sum;
                }
                if (sum - target < 0) {
                    lo++;
                } else {
                    hi--;
                }
            }
        }
        return target - off;
    }

    public static void main(String[] args) {
        ThreadLocalRandom rand = ThreadLocalRandom.current();
        int[] a = new int[10];
        for (int i = 0; i < a.length; i++) {
            a[i] = rand.nextInt(100);
        }
//        System.out.println(new LC16().threeSumClosest(a, rand.nextInt(300)));
//        System.out.println(new LC16().threeSumClosest(new int[]{-1,2,1,-4}, 1));
//        System.out.println(new LC16().threeSumClosest(new int[]{-1,2,1,-4}, 1));
//        System.out.println(new LC16().threeSumClosest(new int[]{-1,2,1,-4}, 4));
        System.out.println(new LC16().threeSumClosest(new int[]{-1, 2, 1, -4}, -9));
    }
}
